Finding the solution to a set of simultaneous linear equations is generally required in numerous scientific and engineering problems. The linear solver, which achieves such a goal, can be commonly used in least square regression for sensor data, digital signal/video processing, model predictive control, and real-time circuit simulation. It can also find wide applications in mathematical computing such as finding the inverse of a matrix, computing determinants or ranks of matrices, etc.
A system of linear equations can be arranged into a matrix form, where each equation becomes a row in the matrix. While all variables can be placed into a column vector, x, the coefficients associated with the variables in all equations can constitute a matrix, A. An additional column vector, b, is added to the right hand side. A system of linear equations can be generally represented in the matrix format by
            [                                                  a              11                                                          a              12                                                          a              13                                            …                                              a                              1                ⁢                N                                                                                        a              21                                                          a              22                                                          a              23                                            …                                              a                              2                ⁢                N                                                                                        a              31                                                          a              32                                                          a              33                                            …                                              a                              3                ⁢                N                                                                          …                                …                                …                                …                                …                                                              a                              N                ⁢                                                                  ⁢                1                                                                        a                              N                ⁢                                                                  ⁢                2                                                                        a                              N                ⁢                                                                  ⁢                3                                                          …                                              a              NN                                          ]        ⁡          [                                                  x              1                                                                          x              2                                                                          x              3                                                            …                                                              x              N                                          ]        =      [                                        b            1                                                            b            2                                                            b            3                                                …                                                  b            N                                ]  In short, this can be described as Ax=b, where A is an N×N matrix, b is an N×1 vector, and x is an N×1 vector.
There exist two major methods to solve the linear systems: direct method and iterative method. Direct methods include LU factorization, QR factorization, Cholesky factorization, etc., which can be typically used for dense linear systems. Iterative methods may include Jacobi, Gauss-Seidel and relaxation iterations, which are suitable for sparse linear systems. This disclosure considers a direct linear solver and its real-time hardware implementation which aims to accelerate the solution procedure by use of parallelism. Also, efficient solution is essential to real-time applications, where all the calculations must be finished within the given time step.
In traditional direct methods, a popular approach is Gaussian elimination method. The Gaussian elimination procedure is to update the matrix continuously by applying a sequence of basic row operations to the lower portion of the matrix until the lower left-hand corner of the matrix becomes filled with zeros. Three types of basic row operations include swapping two rows, multiplying a row by a coefficient, and subtracting a multiple of one row from another row. Following a series of operations, a matrix can be transformed into an upper triangular matrix. A backward substitution process is then applied to find the solution in sequence based on the upper triangular matrix.
A further-reduced method, called Gauss-Jordan Elimination, is to eliminate one column in all rows except the pivot value or diagonal entry within each iteration loop, which can be set to 1 by normalizing each row. The resultant updated matrix after all elimination iterations will be a unit diagonal matrix, so the backward substitution is not needed. The solution will be the last column of the updated augmented matrix, i.e., the solution value in each row is the last value of that particular row vector. This method is not preferred in software solution because it involves more arithmetic operations than the Gaussian elimination method. But on parallel processing hardware the Gauss-Jordan method is more efficient because the hardware allows for parallel processing and elimination of all rows without increasing the processing time.
Field programmable gate arrays (FPGAs) are a type of modern integrated circuit (IC) devices consisting of a large number (e.g., millions) of reconfigurable logic units, as well as many programmable input/output blocks and interconnects. These FPGA devices allow the user to configure their operations through software codes that are written in hardware description languages (HDL) such as VHDL or Verilog. Nowadays, user-friendly, high-level programming tools, such as Xilinx System Generator, are available to be used to program these reconfigurable logic devices, which can help reduce the product development time and costs.
Since programmable logic arrays on FPGAs are massive parallel units, they naturally allow for parallel processing of a large amount of data. Clock signals generated from high-frequency oscillators enable data processing and operation with a clock cycle of as low as 5 ns. Another associated benefit is that FPGAS provide deterministic computation, which makes the timing control easy, especially in real-time implementation.
The present application discloses a hardware based implementation of a direct linear system solver based on FPGA. The disclosed solver directly solves systems of linear equations by applying the Gauss-Jordan Elimination method to an augmented matrix recursively. The hardware accelerator can exploit the inherent parallelism in the algorithm finding the solution, offering efficient implementation of the linear solver.